package com.example.hot100;

/**
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *  每行的元素从左到右升序排列。
 *  每列的元素从上到下升序排列。
 *
 *  示例 1：
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
 * 输出：true
 *
 *  示例 2：
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
 * 输出：false
 */
public class Leetcode240_SearchMatrix {
    public static void main(String[] args) {
        int[][] matrix = {
                { 1,  4,  7, 11, 15},
                { 2,  5,  8, 12, 19},
                { 3,  6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}};
        int target = 5;

        target = 20;

        System.out.println(new Solution().searchMatrix(matrix, target));
    }

    static class Solution {
        /**
         * 解法二:
         * @param matrix
         * @param target
         * @return
         */
        public boolean searchMatrix2(int[][] matrix, int target) {
            int rows = matrix.length;
            int columns = matrix[0].length;
            if (rows * columns == 0) return false;
            int curRow = 0, curCol = columns - 1;
            while (curRow < rows && curCol >= 0) {
                if (matrix[curRow][curCol] > target) {
                    --curCol;
                } else if (matrix[curRow][curCol] < target) {
                    ++curRow;
                } else {
                    return true;
                }
            }
            return false;
        }

        /**
         * 分治算法
         * 由于矩阵行列都是递增的，
         * 遍历矩阵的对角线上的元素
         * 若该元素小于目标 target元素，则它的左上所有元素都小于target
         * 若该元素大于目标 target元素，则它的右下所有元素都大于target
         * 即不用再去左上和右下的区域
         * 只需要在右上和左下进行递归查找即可
         * @param matrix
         * @param target
         * @return
         */
        public boolean searchMatrix1(int[][] matrix, int target) {
            int rows = matrix.length;
            int columns = matrix[0].length;
            if (rows * columns == 0) return false;
            return searchMatrix(matrix, 0, 0, rows - 1, columns - 1, target);
        }

        private boolean searchMatrix(int[][] matrix, int startRow, int startCol, int endRow, int endCol, int target) {
            if (startRow > endRow || startCol > endCol) return false;
            // matrix[startRow][startCol] > target说明当前矩阵的最小值都比target大，则直接返回false
            // matrix[endRow][endCol] < target 说明当前矩阵的最大值都比target小，则直接返回false
            if (matrix[startRow][startCol] > target || matrix[endRow][endCol] < target) return false;

            int diagonalLen = Math.min(endRow - startRow + 1, endCol - startCol + 1); // 对角线的长度(矩阵的行列可能不等)
            for (int i = 0; i < diagonalLen; i++) {// 在对角线上查找元素
                if (matrix[startRow + i][startCol + i] == target) return true;
                if (i == diagonalLen - 1 || matrix[startRow + i + 1][startCol + i + 1] > target) { // 当当前对角线的元素比target元素要大时
                    return searchMatrix(matrix, startRow, startCol + i + 1, startRow + i, endCol, target) // 右上区域
                            || searchMatrix(matrix, startRow + i + 1, startCol, endRow, startCol + i, target); // 左下区域
                }
            }
            return false;
        }

        public boolean searchMatrix(int[][] matrix, int target) {
            return searchMatrix2(matrix, target);
        }
    }
}
